public class Heapsort {


    public static void Heapsort(int[] elem){
        GreatHeap(elem);
        for (int i = elem.length-1; i > 0; i--) {
            swap(elem,0,i);
            siftDown(elem,0,i);
        }
    }
    public static void GreatHeap(int[] elem){
        for (int parent =(elem.length-1-1)/2; parent >=0 ; parent--) {
            siftDown(elem,parent,elem.length-1);
        }
    }

    private static void siftDown(int[] elem,int parent,int len){
        int child = 2*parent +1;
        while (child < len){
            if (child +1 < len && elem[child] < elem[child+1]){
                child++;
            }
            if (elem[child] > elem[parent]){
                swap(elem,parent,child);
                parent = child;
                child = 2*parent +1;
            }else break;
        }

    }
    private static void swap(int[] array,int i,int j){
        int tem = array[i];
        array[i] = array[j];
        array[j] = tem;
    }
}